1. Field of the Invention
The present invention relates to the field of imaging, particularly computer assisted imaging, the correction of computer assisted imaging, the correction of computer assisted imaging having image data that has been block transform encoded, and the removal of artifacts in the block transform encoded segments of the image.
2. Background of the Art
Images contain large volumes of information and the storage or transfer of the images and the information using telecommunication systems and computers consumes many resources. Accordingly, there has been much interest in image compression. Many of the compression schemes involve representing the image as encoded blocks and then compressing each of the encoded blocks or groups of encoded blocks. In other words, the image is divided into a collection of identically sized rectangles within which the image data is transformed to provide a sequence of coefficients that can be encoded with a different number of bits for each coefficient. The number of bits is selected to reduce the amount of redundant or near redundant data that is retained. Non-limiting examples of transforms that can be used for such encoding include the Fourier transform, the cosine transform, the Hadamard transform, or the Haar transform and other wavelet transforms. One of the most popular variants of transforms involves use of the discrete cosine transform (DCT) and is commonly known as “JPEG” after the Joint Photographic Experts Group (ISO/IEC JTC1 SC29 Working Group 1) that originated it. When associated with a file format, JPEG is called JFIF or SPIFF. JPEG is embodied in ISO Standard IS 10918-3. JPEG calls for subdividing the image into blocks, transforming the array of pixel values in each block according to the DCT so as to generate a plurality of coefficients, quantizing the coefficients for each block, and entropy encoding the quantized coefficients for each block. A particularly informative description can be found in G. K. Wallace, “The JPEG still picture compression standard”, Commun. ACM, 34, 30 (1991). A related standard exists for video streams and is known as MPEG.
To achieve large amounts of compression, block transform coding is generally lossy, meaning that image information is permanently discarded during compression and the original image cannot be perfectly reconstructed from the compressed version. When the amount of compression is low, the loss of information is slight and unobjectionable. However, at higher compression levels, the information loss becomes increasingly apparent and is associated with the occurrence of visible artifacts relating to the block nature of the encoding and to the quantization of DCT coefficients. JPEG also tries to take advantage of human vision, which perceives less detail in color than in brightness, and so encodes chrominance in larger blocks than those used for luminance. This leads to additional artifacts at high compression. Artifacts can take any of several forms, including:                Block artifacts, where the outlines of the encoding blocks are superimposed on the image as distinct transitions from one block to another.        Ringing, which involves a spatial oscillation in brightness in the vicinity of sharp, high contrast edges such as occur with line art or text, or in photographs where bright areas are adjacent to dark ones.        Color leakage, where color spills beyond the boundaries of an object into the surroundings, an effect particularly prominent in objects containing saturated red colors.        Checkerboarding, a pixel-level pattern in the image superimposed on an individual encoded block, which can be especially objectionable in images containing smooth skin areas.        
Artifacts, in other words elements in the compressed picture that were not present in the original, tend to be perceived as especially unpleasant. However, these artifacts are also accompanied by other defects that, while not strictly artifacts, are also the result of compression and contribute to reduced image quality, exacerbating the adverse effects of the artifacts. Examples of these additional effects include:                Desaturation, where the vividness of the original colors is reduced by sampling chrominance using larger blocks than for luminance, especially in areas that are small compared to the size of the encoding block.        Blurring or loss of sharpness as high frequency detail is increasing eliminated at higher compression levels.        
Since information is discarded during compression, it generally is impossible to exactly restore the original image. However, it is, in principle, possible to improve its quality. Practitioners of the imaging art have been well aware of compression artifacts and there have been many attempts to reduce them. Most attempts, however, have been directed at removing only a single artifact, typically the block artifact. Other efforts include suppression of “mosquito noise”, a phrase typically used to mean ringing, but the phrase is sometimes used as a catch-all name for ringing and color leakage. However, there remains a need for a method of comprehensively suppressing a range of different artifacts and defects.
One approach to ameliorating artifacts in, for example, MPEG encoded images, takes advantage of the temporal properties of the video stream. This procedure is illustrated by U.S. Pat. No. 5,852,475. Such methods are valueless for still imagery where there is no temporal information. A second approach to ameliorating artifacts has been to change the encoding and decoding algorithm or to transmit additional error correction information along with the image. This, however, is useless for coping with existing JPEG or other block encoded imagery. Another approach ameliorates artifacts by a post-processing that takes advantage of the DCT coefficients stored in the compressed file, as exemplified by U.S. Pat. No. 5,850,294 or U.S. Pat. No. 5,737,451. Many experienced users of images are aware of the lossy character of JPEG compression and immediately convert their images to non-lossy file formats to inhibit further image degradation during editing. In this case, the original file is lost and there is no further access to the DCT coefficients, rendering these methods useless as well. Other less experienced users edit JPEG compressed images and resave them in compressed form. This method is found to cause a situation where artifacts become increasing pronounced during the editing process and require suppression. However, after editing, the image is far removed from the original. Again, access to the discrete cosine transform (DCT) coefficients is impossible but, in this case, also irrelevant. Even the location of the image blocks cannot be taken for granted, since images are frequently cropped arbitrarily or resized. It is highly desirable, therefore, to have a method of artifact suppression that would be effective even under these adverse conditions and this is the concern of the present invention.
U.S. Pat. No. 5,367,385 discloses a seam filter for suppressing the visibility of block edges. The coefficients of the filter are selected based on the properties of the DCT coefficients, and the direction of the filter is selected in relation to the direction of image feature edges in the vicinity of block borders. U.S. Pat. No. 5,920,356 describes a post-processor for digital video that reduces blocking and mosquito noise artifacts. Pixels are classified into categories of image feature edge, block edge and shade area pixels and then are filtered with a spatially adaptive filter whose additional properties are determined from the encoding data. Preferably, the edge characteristics are supplemented by temporal information. U.S. Pat. No. 6,167,164 concerns a method for reduction of a blocking effect by unidirectional weighted filtering. The filter weights are derived from an edge map that is first thresholded using a threshold dependent on the DCT quantization step. The objective of WO 9841025 is to provide an adaptive filter that suppresses block edge artifacts without affecting image feature edges. The number of pixels included in the filtering depends on differences in pixel values across the block boundary and on the size of the quantization step of the DCT coefficients. U.S. Pat. No. 5,454,051 teaches improvement of image quality in a block transform encoded image by adaptively blurring in a way dependent on the coefficients of the transformed data. U.S. Pat. No. 5,495,538 discloses a means of JPEG image artifact reduction in which image blocks are segmented into uniform regions and smoothed. Subsequently the smoothed block is again subjected to DCT in order to guarantee that DCT coefficients will be within the initial quantization interval. A related patent, U.S. Pat. No. 5,521,718, also uses the technique filtering and then checking the result for plausibility against the original DCT coefficients. WO 0022834 describes blocking effect reduction by means of deriving both a local and a global blockiness measure along with estimation of signal to noise ratio from DCT quantization values. This information is used to control a de-blocking filter. U.S. Pat. No. 6,151,420 describes minimizing blocking artifacts by forming overlapping blocks that are filtered. The patent teaches a method of “stitching” the blocks in the region of overlap to improve image appearance. The specific filter disclosed is a Wiener filter applied in the domain of DCT coefficients. Eur. Pat. 808068 claims a method of removing a blocking effect comprising the steps of: extracting the boundary pixels of a current block and each adjacent block; forming difference values between the boundary pixels of the current block and the adjacent ones; calculating the mean of these differences and restricting this mean to within half a quantization step size; and adding this restricted mean to the boundary pixels of the current block. J. Hu, N. Sinaceur, F. Li and Z. Fan, “A simplified approach to reduce compression artifacts in transform coded images”, IEEE Internat. Conf. Acoustics, Speech and Signal Processing, 4, 2565 (1997) present an algorithm with these main elements: block classification; boundary low-pass filtering and mid-point displacement interpolation; edge detection and filtering; and DCT constraint. The block classification is done in the DCT coefficient domain. In contrast to the present invention, all these publications depend on access to the original block transform coefficients.
Additional art of relevance to the present application can be found in these publications. U.S. Pat. No. 5,819,035 relates to removal of ringing artifacts in DCT coding and claims use of anisotropic diffusion filtering for this purpose for use in a video signal decoding system. U.S. Pat. No. 5,802,218 concerns reduction of mosquito and blocking artifacts in video. It uses a filter whose characteristics are determined by a signal variance, a predetermined noise variance and a predetermined autocorrelation coefficient. U.S. Pat. No. 5,883,983 describes filtering method for reducing blocking effects and ringing noise in which an edge map is formed from the image and the image is filtered. The filter properties depend on whether the area in the filter window is homogeneous or not as judged from the edge map, and if not the filter parameters are modified based on the edge map information. U.S. Pat. No. 5,974,197 teaches a closely related procedure. European Pat. 0 881 837 describes a procedure for reducing block coding artifacts by filtering, wherein the characteristics of the filter are determined using fuzzy logic. Input to the fuzzy logic decision unit is in the form of local and global block features computed with a Sobel edge-detecting filter. In Japanese Pat. 11-298898 a correlation value and direction between pixels is determined based on the direction of smallest signal difference between a pixel of interest and surrounding pixels. If the correlation value is below a threshold and the pixel is on a block boundary, it is low-pass filtered along the correlation direction. This procedure has the advantage that block distortion due to diagonal frequency components is prevented. European Pat. 0 886 444 claims a method of filtering a block encoded image comprising detecting a level of block distortion and filtering in dependence on the level of block distortion. The disclosure teaches estimation of block distortion using three pixels on either side of the block boundary and forming a ratio of the absolute differences across the block boundary to those within block boundaries in both adjacent blocks. This estimate is refined using temporal information from preceding and succeeding video frames. The visibility of the block boundary is suppressed with a one-dimensional averaging window in which the weights are chosen based on the block distortion measure. U.S. Pat. No. 5,734,757 discloses a post-processing method for improving block encoded images where a result image pixel is formed from an original image pixel or a filtered image pixel. The result contains pixels from the original image if the absolute difference between filtered and original pixel values is below a threshold, and from the filtered image otherwise. The filter is “a conventional low pass filter such as a median filter or a Laplacian filter”. European Pat. 0 884 911 discloses a method of suppressing block boundaries in which a reference linear interpolation is established between two blocks across their mutual boundary and the intensities of pixels are adjusted towards this interpolation to an extent that depends on their distance from the block edge and on the activity within blocks. European Pat. 0 998 146 describes a method of block edge detection in the horizontal and vertical directions. In any given direction the image is high pass filtered and signal sums are accumulated in a perpendicular direction. The sum is a histogram of edge activity along one direction of the image. Peak positions within the histogram represent the locations of block boundaries (as shown in FIGS. 2 and 3 of the patent). In the best mode for carrying out the invention, the detection of peaks is described thus: “detecting part 18 detects three data higher in an accumulation/addition level in the selected detection region 119 as peak positions”. What this actually means is unclear. For example, it is not evident whether the “accumulation/addition level” refers to the previous accumulation of sums to form the histogram or some action that is part of peak detection, though elsewhere the patent states “periodicity detecting means for detecting periodicity of the block noise in accordance with an accumulation/addition result outputted from the accumulating/adding means” clearly suggesting the former interpretation. Moreover, the use of the word “higher” in connection with peak detection implies some form of thresholding, with values higher than a threshold being taken as peaks. Subsequently the patent teaches binarization according to peak positions, which definitely implies thresholding. European Pat. 1 001 608 claims a method of detecting if an image is compressed. The method involves computing the absolute differences between neighboring pixels in an image, dividing these into groups that cross block boundaries and those that do not, and determining the presence of compression from the statistics of the two groups. The filter described by Y. Itoh, “Detail-preserving noise filtering using a binary index”, Proc. SPIE, 2666, 119 (1996) is based on a binary heterogeneity index. Each pixel is classified into a high activity or a low activity group based on local statistics so that filtering can be restricted only to homogeneous regions. M. Datcu, G. Schwarz, K. Schmidt and C. Reck, “Histogram analysis of JPEG compressed images as an aid in image deblocking”, Proc. DCC '95 Data Compress. Conf, 425 (1995) describe a measure of blocking effect, defined as the area of spikes to the total area of the image histogram. In R. Castagno and G. Ramponi, “A rational filter for the removal of blocking artifacts in image sequences coded at low bitrate”, Proc. VIII European Signal Processing Conference EUSIPCO, 1, 567 (1996) there is presented a filter expressed as a ratio between a linear and a polynomial function of the image data. The filter is capable of changing its behavior from linear smoothing in uniform areas to nonlinear and directional filtering in textured areas. The use of this filter for reduction of blocking artifacts is described in R. Castagno, S. Marsi and G. Ramponi, “A simple algorithm for the reduction of blocking artifacts in images and its implementation”, IEEE Trans. Consumer Electronics, 44, 1062 (1998).